1. Field of the Invention
Apparatuses and methods consistent with the present invention relates to managing mapping information of a nonvolatile memory, and more particularly, to managing mapping information of a nonvolatile memory, in which a time period required for a request for access to a logic sector of the nonvolatile memory is minimized.
2. Description of the Related Art
Generally, embedded systems, such as electric home appliances, communication devices, and set top boxes, widely employ a nonvolatile memory as a storage medium that stores data.
A flash memory, which is mainly used as the nonvolatile memory, is a nonvolatile memory device that can electrically erase or rewrite data. Such a flash memory is widely used as a storage medium for a portable device due to its lower power consumption than a storage medium based on a magnetic disk memory, its fast access time equal to that of a hard disk, and its small size.
Furthermore, the nonvolatile memory can arbitrarily access data stored in a specified position in view of hardware characteristics in the same manner as existing memory devices such as random access memory (RAM) and magnetic storage medium. However, in the case of erasing data, the nonvolatile memory accesses the data in a block unit unlike the existing memory devices. Also, in order to perform writing in a sector in which data are already written, the nonvolatile memory should first erase the whole block including the corresponding sector. This factor deteriorates performance of the nonvolatile memory.
To solve the above problem relating to erase before write, the aforementioned nonvolatile memory supports a logical address and a physical address. In other words, data operation of the logical address, such as reading/writing operation, which is requested from a host, is converted into data operation of the physical address of the actual nonvolatile memory by various mapping algorithms.
A system where the nonvolatile memory is used reconstructs mapping information to reconstruct logical data in accordance with a mapping algorithm when the system is booting. The host searches the position of the physical address, which is mapped with a predetermined logical address, in real time from the nonvolatile memory by referring to the reconstructed mapping information. Thus, the host accesses corresponding data to perform data operation such as reading/writing.
Generally, to maximize performance of the data operation, the nonvolatile memory undergoes two mapping steps. The first mapping step is mapping of a logical unit and a physical unit, wherein a plurality of physical units are mapped with one logical unit. The second mapping step is mapping of a logical sector and a physical sector in each physical unit.
The aforementioned two mapping steps are performed when the system is booting. The host accesses corresponding data through the mapping information reconstructed through the two mapping steps when the data operation of the nonvolatile memory is requested. Also, the mapping information reconstructed through the two mapping steps is updated through the two mapping steps after writing operation of the nonvolatile memory is requested or performed.
FIG. 1 is a view illustrating a related art mapping relation between a logical unit and physical units.
As shown in FIG. 1, physical units 13, 7, 12 and 15 are mapped with a logical unit 0, a physical unit 2 is mapped with a logical unit 1, and physical units 10, 17 and 3 are mapped with a logical unit N. Physical units 20, 1 and, 5 are not mapped with any logical unit. At this time, “Depth” denotes a value showing a use timing of the corresponding physical unit. The physical unit corresponds to the one recently used if its value of “Depth” is great.
FIG. 2 is a view illustrating a mapping relation between a physical sector and a logical sector in a physical unit according to the related art. The case where the mapping relation in the physical unit mapped with the logical unit N in FIG. 1 will exemplarily be described, wherein the logical unit N consists of logical sectors 0, 1, 2, and 3.
As shown in FIG. 2, the physical unit 10 having the greatest value of “Depth” corresponds to one most recently used, and the physical unit 3 having the smallest value of “Depth” corresponds to one first mapped with the logical unit. At this time, the physical sector mapped with the logical sector 0 of the logical unit N becomes the zeroth and the third of the physical unit 3, the physical sector mapped with the logical sector 1 becomes the first of the physical unit 3 and the zeroth and the second of the physical unit 17, the physical sector mapped with the logical sector 2 becomes the second of the physical unit 3 and the first of physical unit 17, and the physical sector mapped with the logical sector 3 becomes the zeroth of the physical unit 17 and the third of the physical unit 10.
The system which uses the nonvolatile memory reconstructs the mapping information through the aforementioned mapping relation when it is booting. The mapping information, as shown in FIG. 3, is comprised of an offset of the physical sector in the physical unit where the logical sector is stored. At this time, since the logical unit N is comprised of logical sectors 0, 1, 2 and 3, the mapping information is comprised of offset of the physical sector for the logical sectors 0, 1, 2 and 3. Accordingly, the mapping information of FIG. 2 according to FIG. 3 is the same as that of FIG. 4. If offset of a plurality of physical sectors exists in one logical sector, the physical sector which is most recently updated is regarded as being valid.
FIG. 5 is a view illustrating a method of processing a reading request in a nonvolatile memory according to the related art. The method of processing a reading request of the logical sector 0 in FIG. 4 will exemplarily be described with reference to FIG. 5.
As shown in FIG. 5, the logical sector 0 is stored in the physical sector 3 of the physical unit 3. Accordingly, to access the logical sector 0, the mapping information of the physical units 10, 17 and 3 should be searched sequentially. Also, to search the physical sector mapped with the logical sector 0, the mapping information should be searched three times.
FIG. 6 is a view illustrating a method of processing a writing request in a nonvolatile memory according to the related art. The method of processing a reading request of the logical sector 0 in FIG. 4 will exemplarily be described with reference to FIG. 6.
As shown in FIG. 6, writing of the logical sector 0 is performed for the physical sector 1 not mapped with the logical sector in the physical unit 10 most recently mapped. At this time, the mapping information of the physical unit 10 is updated because writing is performed for the first physical sector. Also, since the mapping information of the physical unit 10 is updated, the mapping information of the physical sector 3 of the physical unit 3 mapped with the logical sector 0 is also updated, whereby the writing operation is completed.
However, since the aforementioned mapping information is managed per physical unit, many types of mapping information must be searched to search the physical sector mapped with the corresponding logical sector for the reading request and the writing request. Since many memories are used even if the mapping information is updated, there is problem that overhead occurs.
The Korean Patent Unexamined Publication No. 1999-0075161 discloses a method of accessing a flash memory, wherein a memory array is divided into a plurality of operation blocks and each block has a look-up table to improve access time between a logical address and a physical address. This method is to manage mapping information per physical unit but fails to teach a method of solving overhead because many memories for searching and updating mapping information for processing a reading request and a writing request are used.